\documentclass{article}

\usepackage[utf8]{inputenc} %encoding and language
\usepackage[T1]{fontenc}
\usepackage{lmodern}
\usepackage[frenchb]{babel}
\usepackage{graphicx} %graphics and pictures
\usepackage{fancyhdr}
%\usepackage{lastpage}
\usepackage{fancybox} %more boxes
\usepackage{amsmath} %mathematic commands and symbols
\usepackage{amssymb}
\usepackage{mathrsfs}
%\usepackage{enumitem}
\usepackage{xcolor} %colors
\usepackage{stmaryrd} %brackets
\usepackage{listings} %source codes
\usepackage{alltt}

\fancyhead{\rhead{\thepage}}
\fancyfoot{\cfoot{}}
\renewcommand{\headrulewidth}{0pt}
\pagestyle{empty}
\pagestyle{fancy}

\title{Documentation du projet de système digital}
\author{Joran \textsc{Bigalet}, Oscar \textsc{Blumberg} et Pierre \textsc{Cagne}}
\date{}

\begin{document}
\maketitle
\thispagestyle{fancy}

\begin{abstract}
  Ce projet porte sur la conception d'une description de circuits
  logiques synchrones et de la simulation de l'exécution de celui-ci.

  Nous procédons ici en trois étapes : l'écriture aisée du circuit grâce au \emph{JOPml}, la création d'une netlist primaire à partir de celle-ci, puis enfin la simulation de l'exécution du circuit par un simulateur dédié.
\end{abstract}

\tableofcontents
\newpage

\section{Caractérisation d'un circuit logique synchrone}
Cette partie expose la façon de penser le circuit logique synchrone
afin de pouvoir ensuite le traiter algorithmiquement.

Un circuit logique est vu comme la donnée d'un ensemble de \emph{blocs
logiques}\footnote{Par \emph{bloc logique}, on entend tout ensemble de
portes logiques basiques réunies pour former une fonction plus
complexe. Ces blocs peuvent éventuellement être de cardinal 1.} et
d'un ensemble de \emph{points de connexion} qui sont les raccords
entre les blocs. Ainsi, on ne désignera jamais une entrée ou une
sortie d'un bloc par un identifiant propre à celle-ci, mais par
l'identifiant de son point de connexion.

Ces points de connexion sont en quelque sorte des
centralisateurs/redistributeurs de bits.Ceci permet notamment de ne
pas se perdre en notation pour désigner les raccords entre les blocs. Au lieu de dire \og la sortie n${}^\circ$1 du bloc X
est connectée à l'entrée n${}^\circ$4 du bloc Y, mais aussi à l'entrée n${}^\circ$2 du
bloc Z \fg, il suffit de dire \og la sortie n${}^\circ$1 du bloc X, l'entrée
n${}^\circ$4 du bloc Y et l'entrée n${}^\circ$2 du bloc Z sont connectées au point 15 \fg.

\section{JOPml}
\emph{JOPml} est une extension du langage \emph{OCaml} créée grâce à l'outil \emph{camlp4}. Il permet de concevoir un circuit logique tout en exploitant la puissance d'\emph{OCaml} (récursivité, boucle d'itération, test conditionnel, \emph{etc}.). 

La compilation du \emph{JOPml} crée en sortie un fichier .nl contenant une netlist primaire composée seulement de portes logiques de base (or, and, not, nor, nand, xor, reg), après avoir vérifié que le circuit était légal (\emph{i.e.} pas de cycle) via un tri topologique sur le graphe sous-jacent au circuit.

\subsection{Syntaxe}

Les primitives rajoutées à \emph{OCaml} permettent de manipuler simplement des circuits, le tout dans l'esprit fonctionnel et persistant.

\begin{itemize}
\item L'operateur \og | \fg{} permet de concatener deux circuits.
\item L'instruction \og < $o_1$, $o_2$ \dots{} ; $v_1$, $v_2$ \dots > \fg{} crée un nouveau circuit ayant les ports $o$ comme sortie et les $v$ comme variables temporaires.
\item On peut ecrire \og $v_1$, $v_2$, \dots{} = $expr$ \fg{} qui crée un nouveau circuit où les ports $v$ sont connectés aux sorties de $expr$.
\end{itemize}

Les circuits sont alors de simples fonctions \emph{OCaml} qui à des (listes de) ports associent des circuits et des sorties. Par exemple :
\begin{verbatim}
let half_add a b =
  < s,c >
    | s = xor a b
    | c = and a b
;;

let full_add a b ci =
  < s,co ; u,v,w >
    | u,v = half_add a b
    | s,w = half_add u ci
    | co = or w v
;;
\end{verbatim}

Le langage supporte également des tableaux de ports de taille variable. Par exemple pour le compteur module $2^n$ :

\begin{verbatim}
(* Compteur à n bits *)
let rec counter n i =
  (* Compteur à 1 bit *)
  let count1 a =
    < s,c ; u >
    | u = xor a s
    | s = reg u
    | c = and a s
  in
  if n = 1 then count1 i
  else (
    < s[0 .. n-1], c_out; c_in >
	   | s[1 .. n-1], c_in = counter (n-1) i
	   | s[0], c_out = count1 c_in
  )
;;
\end{verbatim}
qui définit recursivement un $n$-compteur à partir d'un $(n-1)$-compteur et d'un $1$-compteur.

Des portes spéciales \emph{input} et \emph{output} sont diponibles pour spécifier les entrées et sorties du circuit final.

\subsection{Pour la suite...}

Les points suivants seront normalement disponibles dans le projet final :
\begin{itemize}
\item Gestion des erreurs avec indication d'où elles proviennent (\emph{e.g.} mauvais nombre de sortie à une porte).
\item Declaration automatique des variables temporaires.
\item Pouvoir écrire \og \verb!u = xor (reg a) b! \fg{} (c'est pour l'instant impossible par la faute d'un petit détail technique).
\item ... ?
\end{itemize}


\section{Netlist}
La netlist est générée par l'executable, résultant de la compilation du JOPml, sous la forme d'un fichier .nl. Bien que la netlist ainsi créée ne soit pas destinée à être traitée directement, sa syntaxe ci-dessous décrite, intermédiaire, permet d'y apporter des modifications mineures.

La netlist est une suite d'instructions de la forme :
\begin{itemize}
  \item pour les portes à entrée binaire
  \begin{center}
    \texttt{
      gate in1 in2 out
    }
  \end{center}
  où \texttt{gate} est le type de la porte (\texttt{or}, \texttt{and}, \texttt{xor}, \texttt{nor} ou \texttt{nand}), \texttt{in1} et \texttt{in2} sont les identifiants (string) des entrées et \texttt{out} l'identifiant (string) de la sortie.

  \item pour les portes à entrée unaire
    \begin{center}
      \texttt{
        gate in out
      }
    \end{center}
  où \texttt{gate} est le type de la porte (\texttt{reg} ou \texttt{not}), \texttt{in} est les identifiants (string) de l'entrée et \texttt{out} l'identifiant (string) de la sortie.

  \item pour les trois portes auxiliaires \texttt{zero}, \texttt{one} et \texttt{in} 
    \begin{center}
      \texttt{ gate var }
    \end{center}
    où \texttt{var} est l'identifiant de la variable initialisée à 0 ou 1.

  \item pour la porte \texttt{output} qui symbolise la sortie standard
    \begin{center}
      \texttt{ output @alias }$($\texttt{in}$\ )^+$
    \end{center}
    et qui prend en argument un alias (\texttt{@} suivi d'un string)
    et un nombre d'entrées entier strictement positif.

  \item pour la porte \texttt{input} qui symbolise les entrées du
    circuit logique
    \begin{center}
      \texttt{input @alias out}
    \end{center}
    et qui prend en argument un alias (\texttt{@} suivi d'un string)
    et une sortie.
\end{itemize}

\vspace{0.3cm}
Voici un exemple de netlist :
\begin{verbatim}
        output @S 11 15 
        input @Ci 20 
        input @B 21 
        input @A 22 
        or 14 18 11 
        and 19 20 14 
        xor 19 20 15 
        and 22 21 18 
        xor 22 21 19
\end{verbatim}

\section{Simulateur}
La version 1.0 du simulateur est codé en Java et ne contient pas les optimisations prévues. Il permet néanmoins de simuler une netlist au format précédemment décrit, et remplit les exigences de l'échéance à mi-projet.

Les versions ultérieures intégreront des améliorations notables (décrites ci-après). Une refonte totale du code et un passage à \emph{OCaml} est envisageable pour la version 2.0.

\subsection{Version 1.0}
Cette version du simulateur est basique. Elle prend en entrée la netlist au format .nl et un fichier .nl.input contenant les différents bits d'entrée ainsi que le nombre de \emph{tics} de l'horloge.

\'A chaque \emph{tic}, on cherche à \emph{propager} les bits d'entrée. L'algorithme cherche successivement les portes à passer\footnote{C'est en fait un tri topologique sur le graphe sous-jacent au circuit} et propage ainsi les bits à travers le circuit.

L'algorithme n'est pas optimisé au sens où il fait le tri topologique à chaque \emph{tic} d'horloge.

\subsection{Version 1.2}

\end{document}